\section{Notation, Definitions, and Preliminaries}
\label{s:prelim}

For a tuple $\vec{x} = (x_1, \ldots, x_n) \in \reals^n$, we let $\min\vec{x}$, $\max\vec{x}$, and $\med\vec{x}$ denote the smallest, the largest, and the $\tceil{n/2}$-smallest coordinate of $\vec{x}$, respectively.
%
We let $\vec{x}_{-i}$ %= (x_1, \ldots, x_{i-1}, x_{i+1}, \ldots, x_n)$
be the tuple $\vec{x}$ without $x_i$. For a non-empty set $S$ of indices, we let $\vec{x}_S = (x_i)_{i \in S}$ and $\vec{x}_{-S} = (x_i)_{i \not\in S}$.
%
We write %$\vec{x} = (\vec{x}_{-i}, x_i)$ and $\vec{x} = (\vec{x}_{-S}, \vec{x}_S)$.
%
$(\vec{x}_{-i}, a)$ to denote the tuple $\vec{x}$ with $a$ in place of $x_i$, $(\vec{x}_{-\{i,j\}}, a, b)$ to denote the tuple $\vec{x}$ with $a$ in place of $x_i$ and $b$ in place of $x_j$, and so on. 

\smallskip\noindent{\bf Instances.}
%
Let $N = \{ 1, \ldots, n\}$ be a set of $n \geq 3$ agents. Each agent $i \in N$ has a location $x_i \in \reals$, which is $i$'s private information. We usually refer to a locations profile $\vec{x} = (x_1, \ldots, x_n) \in \reals^n$ as an \emph{instance}.
%
For an instance $\vec{x}$, we say that the agents are arranged on the line according to a permutation $\pi$ if $\pi$ arranges them in increasing order of their locations in $\vec{x}$, i.e., $x_{\pi(1)} \leq  x_{\pi(2)} \leq \cdots \leq x_{\pi(n)}$.
%
In the proof of Theorem~\ref{thm:2fac-gen}, we consider \emph{3-agent instances}, where $n = 3$, and \emph{3-location instances}, where there are three different locations $x_1, x_2, x_3$, and a partition of $N$ into three coalitions $N_1, N_2, N_3$ such that all agents in coalition $N_i$ occupy location $x_i$, $i \in \{1, 2, 3\}$.
%
We usually denote such an instance as $(x_1\sep N_1, x_2\sep N_2, x_3\sep N_3)$.
%
For a set $N$ of agents, we let $\I(N)$ denote the set of all instances, and let $\Ithr(N)$ denote the set of all 3-location instances.


\smallskip\noindent{\bf Mechanisms.}
%
A (deterministic) mechanism $F$ for $K$-Facility Location maps an instance $\vec{x}$ to a $K$-tuple $(y_1, \ldots, y_K) \in \reals^K$, $y_1 \leq \cdots \leq y_K$, of facility locations.
%
We let $F(\vec{x})$ denote the outcome of $F$ for instance $\vec{x}$, and let $F_\ell(\vec{x})$ denote $y_\ell$, i.e., the $\ell$-th smallest coordinate in $F(\vec{x})$. In particular, for 2-Facility Location, $F_1(\vec{x})$ denotes the leftmost and $F_2(\vec{x})$ denotes the rightmost facility of $F(\vec{x})$. %Slightly abusing the notation, 
We write $y \in F(\vec{x})$ to denote that $F(\vec{x})$ has a facility at $y$.
%
A mechanism $F$ is \emph{anonymous} if for all instances $\vec{x}$ and all agent permutations $\pi$, $F(\vec{x}) = F(x_{\pi(1)}, \ldots, x_{\pi(n)})$.
%
Throughout this work, all references to a mechanism $F$ assume a deterministic mechanism, unless explicitly stated otherwise.


\smallskip\noindent{\bf Social Cost.}
%
Given a mechanism $F$ for $K$-Facility Location and an instance $\vec{x}$, the (individual) cost of agent $i$ is
%
\( \cost[x_i, F(\vec{x})] = \min_{1 \leq \ell \leq K}\{ |x_i - F_\ell(\vec{x})| \} \).
%
The (social) cost of $F$ for an instance $\vec{x}$ is
%
\( \cost[F(\vec{x})] = \sum_{i = 1}^n \cost[x_i, F(\vec{x})] \).
%
The optimal cost for an instance $\vec{x}$ is $\min \sum_{i=1}^n \cost[x_i, (y_1, \ldots, y_K)]$, where the minimum is taken over all $K$-tuples $(y_1, \ldots, y_K)$. %\in \reals^K$.

A mechanism $F$ has an approximation ratio of $\rho \geq 1$, if for any instance $\vec{x}$, the cost of $F(\vec{x})$ is at most $\rho$ times the optimal cost for $\vec{x}$.
%
We say that the approximation ratio $\rho$ of $F$ is \emph{bounded} if $\rho$ is either some constant or some (computable) function of $n$ and $K$. 
%(but it does not depend on other parameters of the instance, such as the maximum or the minimum distance between any pair of agents).


\smallskip\noindent{\bf Strategyproofness.}
%and (Partial) Group Strategyproofness.}
%
A mechanism $F$ is \emph{strategyproof} if no agent can benefit from misreporting her location. Formally,
for all instances $\vec{x}$, every agent $i$, and all locations $y$, it holds that
%
\( \cost[x_i, F(\vec{x})] \leq \cost[x_i, F(\vec{x}_{-i}, y)] \).
%
A mechanism $F$ is \emph{group strategyproof} if for any coalition of agents misreporting their locations, at least one of them does not benefit. Formally,
for all instances $\vec{x}$, every coalition of agents $S$, and all subinstances $\vec{y}_S$, there exists some agent $i \in S$ such that
%
\( \cost[x_i, F(\vec{x})] \leq \cost[x_i, F(\vec{x}_{-S},\vec{y}_S)] \).
%
A mechanism $F$ is \emph{partial group strategyproof} if for any coalition of agents that occupy the same location, none of them can benefit if they misreport their location simultaneously. Formally, for all instances $\vec{x}$, every coalition of agents $S$, all occupying the same location $x$ in $\vec{x}$, and all subinstances $\vec{y}_S$, %it holds that
%
\( \cost[x, F(\vec{x})] \leq \cost[x, F(\vec{x}_{-S}, \vec{y}_S)] \).

By definition, any group strategyproof mechanism is partial group strategyproof, and any partial group strategyproof mechanism is strategyproof.
In \cite[Lemma~2.1]{LSWZ10}, it is shown that any strategyproof mechanism for $K$-Facility Location is also partial group strategyproof (see also \cite[Section~2]{Moul80}).


\smallskip\noindent{\bf Image Sets.}
%
Given a mechanism $F$, the \emph{image} (or option) \emph{set} $I_i(\vec{x}_{-i})$ of an agent $i$ with respect to an instance $\vec{x}_{-i}$ is the set of facility
locations the agent $i$ can obtain by varying her reported location. Formally,
%
\( I_i(\vec{x}_{-i}) = \{ a \in \reals: \exists y \in \reals \mbox{ such that } F(\vec{x}_{-i}, y) = a \} \).
%
One can show that if $F$ is strategyproof, any image set $I_i(\vec{x}_{-i})$ is a collection of closed intervals, and that $F$ allocates a facility to the location in $I_i(\vec{x}_{-i})$ nearest to the location of agent $i$. Formally, for all agents $i$, all instances $\vec{x}$, and all locations $y$, %it holds that
%
\( \cost[y, F(\vec{x}_{-i}, y)] =
\inf_{a \in I_i(\vec{x}_{-i})}\{|y - a|\} \).
%
In \cite[Section~3.1]{LSWZ10}, it is shown that using partial group strategyproofness, we can extend the notion of image sets and the properties above to coalitions of agents that occupy the same location in an instance $\vec{x}$.

Any (open) interval in the complement of an image set $I \equiv I_i(\vec{x}_{-i})$ is called a \emph{hole} of $I$. Given a location $y \not\in I$, we let $l_y = \sup_{a \in I} \{ a < y\}$ %be the location in $I$ nearest to $y$ on the left,
and let $r_y = \inf_{a \in I} \{ a > y\}$. %be the location in $I$ nearest to $y$ on the right.
Since $I$ is a collection of closed intervals, $l_y$ and $r_y$ are well defined and satisfy $l_y < y < r_y$. For convenience, given a $y \not\in I$, we refer to the interval $(l_y, r_y)$ as a $y$-hole in $I$.


\smallskip\noindent{\bf Nice Mechanisms.}
%
For simplicity, we use the term \emph{nice mechanism} to refer to any mechanism $F$ that is deterministic, strategyproof, and has a bounded approximation ratio. We usually refer to a nice mechanism $F$ without explicitly mentioning its approximation ratio, with the understanding that given $F$ and the set $N$ of agents, we can determine an upper bound $\rho$ on the approximation ratio of $F$ for instances in $\I(N)$.

Any nice mechanism $F$ for $K$-Facility Location is \emph{unanimous}, namely for all instances $\vec{x}$ where the agents occupy $K$ different locations $x_1, \ldots, x_K$, $F(\vec{x}) = (x_1, \ldots, x_K)$. %since otherwise $F$ would not have a bounded approximation ratio.
%
Similarly, any hole in an image set $I_i(\vec{x}_{-i})$ of $F$ is a bounded interval. Otherwise, %i.e., if there was an image set $I_i(\vec{x}_{-i})$ with a hole that extends either to $-\infty$ or to $+\infty$, then
%
we could move agent $i$ sufficiently far away from the remaining agents, and obtain an instance for which $F$ would have approximation ratio larger than $\rho$. %Therefore, if $F$ is a nice mechanism, for any instance $\vec{x}$ and any agents $i$, there is a sufficiently small (resp. large) $a$, such that if $i$ moves to $a$, $F$ allocates a facility to $a$, i.e, $a \in F(\vec{x}_{-i}, a)$.


\smallskip\noindent{\bf Well-Separated Instances.}
%
Given a nice mechanism $F$ for $K$-Facility Location with approximation ratio $\rho$, a $(K+1)$-agent instance $\vec{x}$ is \emph{$(i_1|\cdots|i_{K-1}|i_K, i_{K+1})$-well-separated} if $x_{i_1} < \cdots < x_{i_{K+1}}$ and $\rho(x_{i_{K+1}} - x_{i_K}) < \min_{2 \leq \ell \leq K} \{ x_{i_\ell} - x_{i_{\ell-1}} \}$.
%
%Similarly, a $(K+1)$-agent instance $\vec{x}$ is \emph{$(i_1, i_2|i_3|\cdots|i_K|i_{K+1})$-well-separated} if $x_{i_1} < x_{i_2} < \cdots < x_{i_K} < x_{i_{K+1}}$ and $\rho(x_{i_{2}} - x_{i_1}) < \min_{3 \leq \ell \leq K+1} \{ x_{i_\ell} - x_{i_{\ell-1}} \}$.
%
%At the conceptual level, in a well-separated instance, there is a pair of nearby agents whose distance to each other is less than $1/\rho$ times the distance between any other pair of consecutive agent locations on the real line. Therefore any mechanism with an approximation ratio of at most $\rho$ should serve the two nearby agents by the same facility, and serve each of the remaining ``isolated'' agents by a different facility.


%since the distance of $x_i$ to $x_j$ is larger than $R$ times the distance of $x_j$ to $x_k$, any $R$-approximate mechanism should use its leftmost facility for serving $x_i$ and its rightmost facility for  serving $x_j$ and $x_k$. The crux of our characterization is to show that the only incentive-compatible way of selecting the location of the facility serving $x_j$ and $x_k$ is to use a generalized median mechanism with its weights essentially determined by $x_i$!


\smallskip\noindent{\bf Properties.}
%
Next, we obtain some useful properties of nice mechanisms for $K$-Facility Location. %applied to instances with $K+1$ agents.
The proofs of the following propositions are deferred to Appendix~\ref{app:moves}.

\begin{proposition}\label{prop:middle}
Let $F$ be a nice mechanism for $K$-Facility Location. For any $(K+1)$-location instance $\vec{x}$ with $x_{i_1} < \cdots < x_{i_{K+1}}$, $F_1(\vec{x}) \leq x_{i_2}$ and $F_K(\vec{x}) \geq x_{i_K}$.
\end{proposition}

\begin{proposition}\label{prop:interval}
Let $F$ be any nice mechanism for $K$-Facility Location, and let $\vec{x}$ be any $(i_1|\cdots|i_{K-1}|i_K, i_{K+1})$-well-separated instance. Then, $F_K(\vec{x}) \in [x_{i_K}, x_{i_{K+1}}]$.
\end{proposition}

The following propositions show that if there exists an $(i_1|\cdots|i_{K-1}|i_K, i_{K+1})$-well-separated instance $\vec{x}$ with $F_K(\vec{x}) = x_{i_K}$ (resp. $F_K(\vec{x}) = x_{i_{K+1}}$), then as long as we ``push'' the locations of agents $i_K$ and $i_{K+1}$ to the right (resp. left), while keeping the instance well-separated, the rightmost facility of $F$ stays with the location of agent $i_K$ (resp. $i_{K+1}$). The proofs can be found in the Appendix, Section~\ref{app:s:push_right} and Section~\ref{app:s:push_left}, respectively.
%
We should highlight that one can establish the equivalent of the following propositions for well-separated instances where the two nearby agents are located elsewhere in the instance (e.g., the nearby agents are the two leftmost agents, or the second and third agent from the left, instead of the rightmost ones).



\begin{proposition}\label{prop:right_cover}
Let $F$ be any nice mechanism for $K$-Facility Location, and let $\vec{x}$ be any $(i_1|\cdots|i_{K-1}|i_K, i_{K+1})$-well-separated instance such that $F_K(\vec{x}) = x_{i_K}$. Then for every $(i_1|\cdots|i_{K-1}|i_K, i_{K+1})$-well-separated instance $\vec{x}' = (\vec{x}_{-\{i_K, i_{K+1}\}}, x'_{i_K}, x'_{i_{K+1}})$ with $x_{i_K} \leq x'_{i_K}$, it holds that $F_K(\vec{x}') = x'_{i_K}$\,.
\end{proposition}

\begin{proposition}\label{prop:left_cover}
Let $F$ be any nice mechanism for $K$-Facility Location, and let $\vec{x}$ be any $(i_1|\cdots|i_{K-1}|i_K, i_{K+1})$-well-separated instance such that $F_K(\vec{x}) = x_{i_{K+1}}$. Then for every $(i_1|\cdots|i_{K-1}|i_K, i_{K+1})$-well-separated instance $\vec{x}' = (\vec{x}_{-\{i_K, i_{K+1}\}}, x'_{i_K}, x'_{i_{K+1}})$ with $x'_{i_{K+1}} \leq x_{i_{K+1}}$, it holds that $F_K(\vec{x}') = x'_{i_{K+1}}$\,.
\end{proposition} 